#include <iostream>
using namespace std;

struct TreeLinkNode {
    TreeLinkNode *left;
    TreeLinkNode *right;
    TreeLinkNode *next;
    int val;

    TreeLinkNode(int _val){
        left = NULL;
        right = NULL;
        next = NULL;
        val = _val;
    }
};

void LinkNext(TreeLinkNode *root, TreeLinkNode *cur, int depth, unsigned int pathCode){
    unsigned int tmpCode = pathCode;
    int tmpDepth = depth;
    TreeLinkNode *curPoint = root;
    while(tmpDepth > 0 && curPoint){
        int leftRight = tmpCode & (0x1<<(tmpDepth-1));
        if(leftRight==0){
            // left
            curPoint = curPoint->left;
        }
        else{
            curPoint = curPoint->right;
        }
        --tmpDepth;
    }
    if(!curPoint)
        return;
    cur->next = curPoint;
    ++pathCode;
    if((pathCode>>depth)!=0){
        curPoint->next = NULL;
        return;
    }
    LinkNext(root, curPoint, depth, pathCode);
}



void connect(TreeLinkNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(!root)
        return;
    TreeLinkNode *cur = root->left;
    int depth = 1;
    while(cur!=NULL){
        LinkNext(root, cur, depth, 0x1);
        ++depth;
        cur = cur->left;
    }
}

int main(){
    TreeLinkNode root(0);
    TreeLinkNode a(1);
    TreeLinkNode a1(3);
    TreeLinkNode a2(4);
 //   a.left = &a1;
 //   a.right = &a2;
    root.left = &a;
    TreeLinkNode b(2);
    TreeLinkNode b1(5);
    TreeLinkNode b2(6);
//    b.left = &b1;
 //   b.right = &b2;
    root.right = &b;

    connect(&root);


    return 0;
}